/**
 * 序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
 * 例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。
 *
 * 给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
 *https://leetcode.cn/problems/verify-preorder-serialization-of-a-binary-tree/
 * 思路：我们可以定义一个概念，叫做槽位。一个槽位可以被看作「当前二叉树中正在等待被节点填充」的那些位置。
 * 二叉树的建立也伴随着槽位数量的变化。每当遇到一个节点时：
 * 如果遇到了空节点，则要消耗一个槽位；
 * 如果遇到了非空节点，则除了消耗一个槽位外，还要再补充两个槽位。
 * 此外，还需要将根节点作为特殊情况处理（将槽位初始为1，因为根节点占一个槽位，如果根节点为空直接返回，不然进入循环）
 */
class IsValidSerializationDieDaiCaoWei {
    public boolean isValidSerialization(String preorder) {
        if(preorder==null){
            return true;
        }
        int len=preorder.length();
        int i=0;
        int slots=1;
        while(i<len){
            if(slots==0){
                return false;
            }
            if(preorder.charAt(i)==','){
                i++;
            }else if(preorder.charAt(i)=='#'){
                i++;
                slots--;//节点为空槽位减少一位
            }else{
                while(i<len&&preorder.charAt(i)!=','){
                    i++;
                }
                slots++;//读到非空节点槽位先减少一位，再增加2位（左右孩子）slots=slots-1+2;
            }
        }
        return slots==0;
    }
}